﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;


//https://leetcode.cn/problems/valid-parentheses/
//20. 有效的括号
//class Solution {
//public:
//    bool isValid(string s) {
//        
//        stack<char> st;
//        size_t i = 0;
//        char tmp = ' ';
//        while (i<s.size())
//        {
//            tmp = s[i];
//            if (tmp == '(' || tmp == '[' || tmp == '{')
//            {
//                st.push(tmp);
//            }
//            else
//            {
//                if (!(st.empty()))
//                {
//                    if ((st.top() == '(' && tmp == ')') ||
//                        (st.top() == '[' && tmp == ']')||
//                        (st.top() == '{' && tmp == '}'))
//                    {
//                        st.pop();
//                    }
//                    else
//                    {
//                        return false;
//                    }
//                }
//                else
//                {
//                    return false;
//                }
//            }
//            i++;
//        }
//        if (st.empty())
//        {
//            return true;
//        }
//        return false;
//    }
//};





//344. 反转字符串
//https://leetcode.cn/problems/reverse-string/description/
//class Solution {
//public:
//    void reverseString(vector<char>& s) {
//        int n = s.size() - 1;
//        for (size_t i = 0; i < n; i++)
//        {
//            swap(s[i], s[n]);
//            n--;
//        }
//    }
//};
//


//905. 按奇偶排序数组
//https://leetcode.cn/problems/sort-array-by-parity/
//class Solution {
//public:
//    vector<int> sortArrayByParity(vector<int>& nums) {
//        int pre = 0;
//        int cur = 0;
//        while (cur < nums.size()) {
//            if (nums[cur] % 2 == 0) {
//                if (cur != pre)
//                    swap(nums[cur], nums[pre]);
//                pre++;
//            }
//            cur++;
//        }
//        return nums;
//    }
//};


//414. 第三大的数
//https://leetcode.cn/problems/third-maximum-number/description/
//class Solution {
//public:
//    int thirdMax(vector<int>& nums) {
//        set<int> s(nums.begin(), nums.end());
//        priority_queue<int, vector<int>> q(s.begin(), s.end());
//        if (q.size() < 3)
//        {
//            return q.top();
//        }
//        int x = 0;
//        for (size_t i = 3; i > 0; i--) {
//            if (q.empty()) {
//                break;
//            }
//            x = q.top();
//            q.pop();
//        }
//        return x;
//    }
//};

//删除有序数组中的重复项
//https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/
//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        int cur = 0;
//        int pucr = 1;
//        int n = nums.size();
//        while (pucr < n)
//        {
//            if (nums[cur] == nums[pucr])
//            {
//                while (pucr < n && nums[cur] == nums[pucr])
//                {
//                    pucr++;
//                }
//                if (pucr >= n)
//                {
//                    break;
//                }
//                cur++;
//                nums[cur] = nums[pucr];
//            }
//            else
//            {
//                cur++;
//            }
//        }
//        return ++cur;
//    }
//};


//7. 破冰游戏
//https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/description/?envType=problem-list-v2&envId=recursion
//class Solution {
//public:
//    void iron(vector<int>& tmp, int target, int begin)
//    {
//        if (tmp.size() == 1)
//        {
//            return;
//        }
//        begin += target - 1;
//        begin = begin % tmp.size();
//        tmp.erase(tmp.begin() + begin);
//        if (begin == tmp.size())
//        {
//            begin == 0;
//        }
//        iron(tmp, target, begin);
//    }
//    int iceBreakingGame(int num, int target) {
//
//        vector<int> tmp;
//        for (size_t i = 0; i < num; i++)
//        {
//            tmp.push_back(i);
//        }
//        iron(tmp, target, 0);
//        return tmp[0];
//    }
//};




//分割链表
//https://leetcode.cn/problems/partition-list-lcci/description/

//struct ListNode {
//      int val;
//      ListNode *next;
//      ListNode() : val(0), next(nullptr) {}
//      ListNode(int x) : val(x), next(nullptr) {}
//      ListNode(int x, ListNode *next) : val(x), next(next) {}
// };
// 
//class Solution {
//public:
//    ListNode* partition(ListNode* head, int x) {
//        ListNode* minhead = nullptr;
//        ListNode* maxhead = nullptr;
//        ListNode* mincur = nullptr;
//        ListNode* maxcur = nullptr;
//
//        while (head)
//        {
//            if (head->val < x)
//            {
//                if (minhead == nullptr)
//                {
//                    minhead = head;
//                    mincur = head;
//                }
//                else
//                {
//                    mincur->next = head;
//                    mincur = mincur->next;
//                }
//            }
//            else
//            {
//                if (maxhead == nullptr)
//                {
//                    maxhead = head;
//                    maxcur = head;
//                }
//                else
//                {
//                    maxcur->next = head;
//                    maxcur = maxcur->next;
//                }
//            }
//            head = head->next;
//        }
//        if (mincur)
//            mincur->next = maxhead;
//        else
//        {
//            return maxhead;
//        }
//        if (maxcur)
//            maxcur->next = nullptr;
//        return minhead;
//    }
//};


//56. 合并区间
//https://leetcode.cn/problems/merge-intervals/description/?envType=problem-list-v2&envId=array

//class Solution {
//public:
//
//    vector<vector<int>> merge(vector<vector<int>>& intervals) {
//        if (intervals.size() < 2)
//        {
//            return intervals;
//        }
//        sort(intervals.begin(), intervals.end());
//        vector<vector<int>> ret;
//        vector<int> tmp;
//        tmp.resize(4);
//        tmp[0] = (intervals[0][0]);
//        tmp[1] = (intervals[0][1]);
//
//        for (size_t i = 1; i < intervals.size(); i++)
//        {
//               
//            tmp[2] = (intervals[i][0]);
//            tmp[3] = (intervals[i][1]);
//                sort(tmp.begin(), tmp.end());
//            if(tmp[0] == intervals[i][0]|| tmp[0] == intervals[i][1]||
//                tmp[1] == intervals[i][0] || tmp[1] == intervals[i][1])
//            {
//                //ret.push_back({ tmp[0],tmp[3] });
//                tmp[1] = tmp[3];
//                if (i == intervals.size() - 1)
//                {
//                    ret.push_back({ tmp[0],tmp[1] });
//                    break;
//                }
//            }
//            else
//            {
//                ret.push_back({tmp[0],tmp[1]});
//                tmp[0] = tmp[2];
//                tmp[1] = tmp[3];
//                if (i == intervals.size() - 1)
//                {
//                    ret.push_back({ tmp[0],tmp[1] });
//
//                }
//            }
//        }
//        return ret;
//        
//    }
//};


//用栈实现队列
//https://leetcode.cn/problems/implement-queue-using-stacks/description/
//class MyQueue {
//public:
//    MyQueue() {
//       
//    }
//
//    void push(int x) {
//        s1.push(x);
//    }
//
//    int pop() {
//        if (s2.empty())
//        {
//            while (!(s1.empty()))
//            {
//                s2.push(s1.top());
//                s1.pop();
//            }
//        }
//        int tmp = s2.top();
//        s2.pop();
//        return tmp;
//         
//    }
//
//    int peek() {
//        if (s2.empty())
//        {
//            while (!(s1.empty()))
//            {
//                s2.push(s1.top());
//                s1.pop();
//            }
//        }
//        return s2.top();
//    }
//
//    bool empty() {
//        return s1.empty() && s2.empty();
//    }
//
//    stack<int> s1;
//    stack<int> s2;
//};

//递归乘法
//https://leetcode.cn/problems/recursive-mulitply-lcci/description/
//class Solution {
//public:
//    int multiply(int A, int B) {
//        if (B == 1)
//        {
//            return A;
//        }
//        return A + multiply(A, B - 1);
//    }
//};



//随机链表的复制
//https://leetcode.cn/problems/copy-list-with-random-pointer/?envType=problem-list-v2&envId=hash-table
//class Node {
//public:
//    int val;
//    Node* next;
//    Node* random;
//
//    Node(int _val) {
//        val = _val;
//        next = NULL;
//        random = NULL;
//    }
//};
//class Solution {
//public:
//    Node* copyRandomList(Node* head) {
//        map<Node*, Node*> dict;
//        Node* phead = nullptr;
//        
//        Node* cur = head;
//        while (cur)
//        {
//            Node* newnode = new Node(cur->val);
//            if (phead == nullptr)
//            {
//                phead = newnode;
//            }
//            dict.insert({ cur,newnode });
//            cur = cur->next;
//        }
//        cur = head;
//
//        while (cur)
//        {
//            Node* pcur = dict[cur];
//            pcur->next = dict[cur->next];
//            pcur->random = dict[cur->random];
//            cur = cur->next;
//        }
//
//        return phead;
//
//    }
//};




//题目一：【验证回文串II】https://leetcode.cn/problems/RQku0D/description/        字节跳动-2024-开发   
//class Solution {
//public:
//    bool ispalindromic(string& s, int left,int right)
//    {
//        while (left < right)
//        {
//            if (s[left] != s[right])
//            {   
//                return false;
//            }
//            left++;
//            right--;
//        }
//        return true;
//    }
//    bool validPalindrome(string s) {
//        int left = 0;
//        int right = s.size()-1;
//     
//        while (left < right)
//        {
//            if (s[left] != s[right])
//            {
//                return ispalindromic(s, left + 1, right) || ispalindromic(s, left, right - 1);
//            }
//            left++;
//            right--;
//        }
//        return true;
//    }
//};


//          
//题目二：【x的平方根】 https://leetcode.cn/problems/jJ0w9p/description/        百度-2024-开发

//class Solution {
//public:
//    int mySqrt(int x) {
//        if (x <= 1)
//        {
//            return x;
//        }
//
//        for (size_t i = 1; i <= x; i++)
//        {
//            if (i * i == x)
//            {
//                return i;
//            }
//            if (i * i > x)
//            {
//                return i - 1;
//            }
//                
//        }
//        return 0;
//    }
//};

//class Solution {
//public:
//	int mySqrt(int x) {
//		if (x <= 1)
//		{
//			return x;
//		}
//
//		unsigned long long mid = x / 2;
//
//		while (mid * mid > x)
//		{
//			mid /= 2;
//		}
//
//		for (size_t i = mid; i <= x; i++)
//		{
//			if (i * i == x)
//			{
//				return i;
//			}
//			if (i * i > x)
//			{
//				return i - 1;
//			}
//
//		}
//		return 0;
//	}
//};
//
//题目一：【最长回文串】https://leetcode.cn/problems/longest-palindrome/description/ "谷歌-2024-开发 字节跳动-2023-开发"

//class Solution {
//public:
//    int longestPalindrome(string s) {
//        if (s.empty())
//        {
//            return 0;
//        }
//        map<char, int> dict;
//        int i = 0;
//        while (i < s.size())
//        {
//           dict[s[i++]]++;
//        }
//        int x = 0;
//        auto it = dict.begin();
//        for (auto& e: dict)
//        {
//            if (e.second % 2 == 1)
//            {
//                e.second--;
//            }
//            x += e.second;
//        }
//        if (x < s.size())
//        {
//            x++;
//        }
//        return x;
//    }
//};
//


//155. 最小栈
//https://leetcode.cn/problems/min-stack/description/

//class MinStack {
//public:
//    MinStack() {
//
//    }
//
//    void push(int val) {
//
//        if (s2.empty() || val <= s2.top())
//        {
//            s2.push(val);
//        }
//        s1.push(val);
//    }
//
//    void pop() {
//        if (!(s2.empty()) && s2.top() == s1.top())
//        {
//            s2.pop();
//        }
//        s1.pop();
//    }
//    int top() {
//        return s1.top();
//    }
//    int getMin() {
//        return s2.top();
//    }
//    stack<int>s1;
//    stack<int>s2;
//
//};



